from typing import List
class Solution:
    def rob(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1], nums[i] + dp[i-2])
        return dp[-1]

if __name__ == '__main__':
    s = Solution()
    print(s.rob([2,7,9,3,1,5,8]))